
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1810. -- [Ioi2005]gar
</title><center><h2>1810: [Ioi2005]gar
</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>27&nbsp;&nbsp;<span class=green>Solved: </span>11<br>[<a href='submitpage.php?id=1810'>Submit</a>][<a href='problemstatus.php?id=1810'>Status</a>][<a href='bbs.php?id=1810'>Discuss</a>]</center><h2>Description</h2><div class=content>Byteman拥有镇上最漂亮的花园。他在自己的花园里面种了N朵玫瑰花。夏天来了，所有的花都开的非常的漂亮。Byteman开始意识到自己没有能力看管自己花园里的所有的花，所以他决定雇佣两个园丁来帮助他。他想在花园中选择两块矩形的区域分别交给两个园丁看管。而且这两个矩形区域必须不能相交或者重叠，并且每一个区域要恰好包含K朵玫瑰花。
Byteman想要给这两块矩形区域的周围安上栅栏，但是他现在手头比较紧，所以他希望自己花的钱尽量的少。你的任务就是帮助Byteman选择两块矩形的区域,使得它们在满足条件的情况下周长和最小。
Byteman的花园有L米长，W米宽。花园被分成了L*W个大小相同(1*1)的方格。我们以平行与花园的两边建立起一个坐标系。所有的方格的坐标(x,y)满足1<=x<=L,1<=y<=W.每个方格内可能会有任意数目的玫瑰。
所选的矩形区域的两边必须跟花园的两边平行，并且矩形区域的四个角的坐标必须是整数。对于1<=L1<=L2<=L 并且 1<=W1<=W2<=W,一个矩形区域的四个角为(L1,W1),(L1,W2),(L2,W1)和(L2,W2):
* 这个矩形内所包含的点的坐标(x,y)满足L1<=x<=L2并且W1<=y<=W2.
* 这个矩形的周长是 2*(L2-11+1)+2*(W2-W1+1).
所选的两块矩形不能重叠或者相交。也就是它们不能有公共的方格。即使它们有公共的边，计算周长的时候也要分别计算。</div><h2>Input</h2><div class=content>
第一行是L和W。1≤L,W≤250。
第二行是N和K。2≤n≤5000,1≤k≤n/2。
接下来N行为N朵玫瑰的坐标。
50%的数据中，W≤40.
</div><h2>Output</h2><div class=content>输出仅有一行，为最小周长。如果不存在满足题意的矩形，则输出’NO’。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>6 5<br />
7 3<br />
3 4<br />
3 3<br />
6 1<br />
1 1<br />
5 5<br />
5 5<br />
3 1	<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>22</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1810'>Submit</a>][<a href='problemstatus.php?id=1810'>Status</a>][<a href='bbs.php?id=1810'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
